package org.example.sort;

import java.util.ArrayList;
import java.util.Arrays;

public class Relative_ordering_of_arrays {
    public static void main(String[] args) {
        //数组的相对排序

        //给定两个数组，arr1 和 arr2，
        //arr2 中的元素各不相同
        //arr2 中的每个元素都出现在 arr1 中
        //对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
        int[] arr1 = {2,3,1,3,2,4,6,7,9,2,19};
        int[] arr2 = {2,1,4,3,9,6};
        int[] ints = relativeSortArray(arr1, arr2);
        System.out.println(Arrays.toString(ints));
    }
    public static int[] relativeSortArray(int[] arr1, int[] arr2) {
        ArrayList<Integer> list = new ArrayList<>();
        boolean[] visited = new boolean[arr1.length];

        for (int i = 0; i < arr2.length; i++) {
            for (int j = 0; j < arr1.length; j++) {
                if (!visited[j] && arr1[j] == arr2[i]){
                    list.add(arr1[j]);
                    visited[j] = true;
                }
            }
        }

        for (int i = 0; i < arr1.length; i++) {
            if (visited[i]) continue;
            for (int j = i+1; j < arr1.length; j++) {
                if (visited[j]) continue;
                if (arr1[i] > arr1[j]){
                    int temp = arr1[i];
                    arr1[i] = arr1[j];
                    arr1[j] = temp;
                }
            }
        }

        for (int i = 0; i < arr1.length; i++) {
            if (visited[i]) continue;
            list.add(arr1[i]);
        }

        int[] array = list.stream().mapToInt((i) -> {
            return i;
        }).toArray();
        return array;
    }
}
